package com.fufu.algorithem.stack;

import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 波兰表达式 Polish Notation(前缀表达式)
 * @author: BlcakTiger
 * @date: 2023/2/13 21:13
 * @contact: hsf6661@163.com
 */
public class PN {

    public static void main(String[] args) {
        //后缀 3 4 + 5 * 6 -  ==> 中缀(3+4)*5-6  ==> 前缀 - * + 3 4 5 6   res=29
        //前缀 - 1 + 2 3 ==》中缀 1-(2+3) ==>后缀 1 2 3 + -  res=-4
        String expression = "- * + 3 4 5 6";
        int i = polishCalculator(expression);
        System.out.println(i);
    }


    /**
     * 波兰计算器
     * @return 返回波兰表达式的值
     */
    public static int polishCalculator(String expression){
        //前缀表达式需要从右往左，为了方便遍历，将其反转
        expression = new StringBuffer(expression).reverse().toString();
        //将表达式拆分成数组
        String[] s = expression.split(" ");

        //创建栈
        Stack<String> stack = new Stack();
        int num1;
        int num2;
        //正则表达式：1-n位数字
        String regex = "\\d+";
        //添加元素到栈中
        for (String s1 : s) {
            //如果是数字
            if (s1.matches(regex)){
                stack.push(s1);
            }else{//操作符
                num1 = Integer.parseInt(stack.pop());
                num2 = Integer.parseInt(stack.pop());
                //前缀表达式要后面的数减前面的数；后缀表达式前面的数减后面的数
                stack.push(""+calc(num1,num2,s1));
            }
        }
        return Integer.parseInt(stack.pop());
    }


    public static int calc(int n,int m,String op){
        switch (op){
            case "+":
                return n + m;
            case "-":
                return n - m;
            case "*":
                return n * m;
            case "/":
                return n / m;
            default:
                return -1;
        }
    }
}
